class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        if len(s1)<len(s2):
            s1,s2=s2,s1
        if len(s1) + len(s2)!=len(s3):
            return False
        if len(s3) == 0:
            return True
        set1 = set()
        set1.add(0)
        for i in range(len(s1)+1):
            tmp = set()
            for j in set1:
                for k in range(j, len(s2)+1):
                    i3 = i + k
                    if i<len(s1) and s3[i3] == s1[i]:
                        tmp.add(k)
                    if i == len(s1) and k == len(s2):
                        return True
                    if k==len(s2) or s2[k] != s3[i3]:
                        break
            set1 = tmp
        return False


if __name__ == '__main__':
    so = Solution()
    # s1 = "aabcc"
    # s2 = "dbbca"
    # s3 = "aadbbcbcac"
    s1 = "aabcc"
    s2 = "dbbca"
    s3 = "aadbbbaccc"
    r = so.isInterleave(s1, s2 ,s3)
    print(r)
